const CASHES: [u32; 8] = [1, 2, 5, 10, 20, 30, 50, 100];


pub fn dp_rec_mc(amount: u32) -> u32 {
    let flag = amount + 1;
    // 例如纸币类型为1, 4, 6, 目标金额9. 贪心是结果是1个6,3个1,总共4张, 但是显然2个4, 1个1, 总共3张更优, 因此使用动态规划
    // dp[i]表示凑齐i金额的最小张数, flag作为没有方案的标记
    let mut dp = vec![flag; amount as usize + 1];
    // 金额0当然是0张
    dp[0] = 0;
    for i in 1..=amount {
        for cash in CASHES {
            if i >= cash && dp[i as usize - cash as usize] != flag {
                dp[i as usize] = dp[i as usize].min(dp[i as usize - cash as usize] + 1);
            }
        }
    }

    dp[amount as usize]
}
